class AStarPathfinding {
    openList = [];
    closedList = [];
    obstacles = [];

    constructor(obstacles = []) {
        this.openList = [];
        this.closedList = [];
        this.obstacles = obstacles;  // 障碍物列表，包含障碍物矩形
    }

    // 计算两点之间的欧几里得距离（使用矩形中心）
    distance(rectA, rectB) {
        const centerA = { x: rectA.x + rectA.width / 2, y: rectA.y + rectA.height / 2 };
        const centerB = { x: rectB.x + rectB.width / 2, y: rectB.y + rectB.height / 2 };
        return Math.sqrt(Math.pow(centerA.x - centerB.x, 2) + Math.pow(centerA.y - centerB.y, 2));
    }

    // 判断是否与障碍物碰撞
    isObstacle(rect) {
        for (let obstacle of this.obstacles) {
            if (this.isRectOverlap(rect, obstacle)) {
                return true;
            }
        }
        return false;
    }

    // A* 寻路
    findPath(startRect, goalRect) {
        // 单个起点
        this.openList.push({ position: startRect, g: 0, h: this.distance(startRect, goalRect), f: 0 });

        while (this.openList.length > 0) {
            // 找到当前 f 值最小的节点
            let currentNode = this.openList.reduce((prev, curr) => prev.f < curr.f ? prev : curr);

            // 如果到达目标，返回路径
            if (this.distance(currentNode.position, goalRect) < 1) {
                return this.reconstructPath(currentNode);
            }

            // 从 openList 移到 closedList
            this.openList = this.openList.filter(node => node !== currentNode);
            this.closedList.push(currentNode);

            // 获取当前节点的邻居节点
            let neighbors = this.getNeighbors(currentNode.position);

            for (let neighbor of neighbors) {
                if (this.closedList.some(node => this.isSamePosition(node.position, neighbor))) {
                    continue; // 已经在 closedList 中
                }

                // 如果邻居节点是障碍物，跳过
                if (this.isObstacle(neighbor)) {
                    continue;
                }

                let tentative_g = currentNode.g + this.distance(currentNode.position, neighbor);

                let existingNode = this.openList.find(node => this.isSamePosition(node.position, neighbor));
                if (!existingNode) {
                    let newNode = {
                        position: neighbor,
                        g: tentative_g,
                        h: this.distance(neighbor, goalRect),
                        f: tentative_g + this.distance(neighbor, goalRect),
                        parent: currentNode
                    };
                    this.openList.push(newNode);
                } else if (tentative_g < existingNode.g) {
                    existingNode.g = tentative_g;
                    existingNode.f = tentative_g + existingNode.h;
                    existingNode.parent = currentNode;
                }
            }
        }

        return [];  // 如果没有找到路径
    }

    // 获取邻居节点：基于当前坐标扩展多个方向的候选矩形，并排除障碍物
    getNeighbors(rect) {
        let step = 10;  // 每次扩展的步长
        let potentialNeighbors = [
            { x: rect.x + step, y: rect.y, width: rect.width, height: rect.height },
            { x: rect.x - step, y: rect.y, width: rect.width, height: rect.height },
            { x: rect.x, y: rect.y + step, width: rect.width, height: rect.height },
            { x: rect.x, y: rect.y - step, width: rect.width, height: rect.height }
        ];

        // 过滤掉与障碍物重叠的邻居
        return potentialNeighbors.filter(neighbor => !this.isObstacle(neighbor));
    }

    // 还原路径
    reconstructPath(node) {
        let path = [];
        while (node) {
            path.push(node.position);
            node = node.parent;
        }
        return path.reverse();  // 从起点到终点
    }

    // 判断两个位置是否相同（矩形位置相同）
    isSamePosition(rectA, rectB) {
        return rectA.x === rectB.x && rectA.y === rectB.y;
    }

    // 矩形碰撞检测函数：判断两个矩形是否重叠
    isRectOverlap(rect1, rect2) {
        return !(rect1.x + rect1.width <= rect2.x ||  // rect1 右边界小于 rect2 左边界
            rect1.x >= rect2.x + rect2.width ||  // rect1 左边界大于 rect2 右边界
            rect1.y + rect1.height <= rect2.y || // rect1 上边界小于 rect2 下边界
            rect1.y >= rect2.y + rect2.height);  // rect1 下边界大于 rect2 上边界
    }

}



// 使用示例：障碍物和起点的矩形
let obstacles = [
    { x: 50, y: 50, width: 20, height: 20 },  // 障碍物1
    { x: 100, y: 100, width: 30, height: 30 },  // 障碍物2
];

// 单个起点的矩形区域
let start = { x: 0, y: 0, width: 10, height: 10 };

// 终点矩形
let goal = { x: 200, y: 200, width: 10, height: 10 };

let astar = new AStarPathfinding(obstacles);
let path = astar.findPath(start, goal);
